package com.atguigu.kruskal;

import java.util.Arrays;

// 好难，跟prim的区别就是找出最小的权值的边来生成最小二叉树。prim是根据任意点来的
public class KruskalCase {

    private static final int INF = 0;

    private int edgeNum;
    private char[] vertexs;
    private int[][] matrix;

    public static void main(String[] args) {
        char[] vertexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

        int matrix[][] = {
                        /* A *//* B *//* C *//* D *//* E *//* F *//* G */
                /* A */ { 0, 12, INF, INF, INF, 16, 14 }, 
                /* B */ { 12, 0, 10, INF, INF, 7, INF },
                /* C */ { INF, 10, 0, 3, 5, 6, INF }, 
                /* D */ { INF, INF, 3, 0, 4, INF, INF },
                /* E */ { INF, INF, 5, 4, 0, 2, 8 }, 
                /* F */ { 16, 7, 6, INF, 2, 0, 9 },
                /* G */ { 14, INF, INF, INF, 8, 9, 0 } };

        
        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
      
        kruskalCase.print();
        kruskalCase.kruskal();

    }

    public void kruskal() {
        int index = 0;
        EData[] edgesList = getEdges();

        EData[] rets = new EData[edgeNum];

        int[] ends = new int[edgeNum];
        sortEdges(edgesList);

        System.out.println("排序: \n");
        for (EData item : edgesList) {
            System.out.println(item.start + "->" + item.end + "->" + item.weight);
        }
        System.out.println("-------------");

        for (int i = 0; i < edgeNum; i++) {
            int p1 = getPosition(edgesList[i].start);//4

            int p2 = getPosition(edgesList[i].end);//5

            int m = getEnd(ends, p1);

            int n = getEnd(ends, p2);
            System.out.println(p1+ "->" + p2 +"->");
            
            System.out.println(m+ "->" + n +"->"+Arrays.toString(ends));
            System.out.println("--------");
            if (m != n) {
                ends[m] = n; 
                // System.out.println(m+ "->" + n +"->"+Arrays.toString(ends));
                rets[index++] = edgesList[i]; 
            }
        }

    }

    /**
     * 功能: 获取下标为i 的顶点的终点(), 用于后面判断两个顶点的终点是否相同
     * 
     * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
     * @param i    : 表示传入的顶点对应的下标
     * @return 返回的就是 下标为i 的这个顶点对应的终点的下标
     */

    private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

    /// 得到边对应的顶点
    public EData[] getEdges() {
        int index = 0;
        EData[] edgesList = new EData[edgeNum];

        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != 0) {
                    edgesList[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return edgesList;
    }

    public void sortEdges(EData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if (edges[j].weight > edges[j + 1].weight) {
                    EData temp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = temp;
                }
            }
        }
    }

    // 得到顶点的位置
    private int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch) {
                return i;
            }
        }

        return -1;
    }

    public void print() {
        System.out.println("邻接矩阵为: \n");
        for (int[] item : matrix) {
            System.out.println(Arrays.toString(item));
        }

    }

   

    public KruskalCase(char[] vertexs, int[][] matrix) {
        // 长度
        int vlen = vertexs.length;

        // 边
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }

        // 矩阵赋值
        this.matrix = new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }
        // 求边的总数
        for (int i = 0; i < vlen; i++) {
            for (int j = i + 1; j < vlen; j++) {
                if (this.matrix[i][j] != INF) {
                    edgeNum++;
                }
            }
        }

    }
}

class EData {
    char start;
    char end;
    int weight;

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}